// 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

// candidates 中的每个数字在每个组合中只能使用一次。

// 说明：

// 所有数字（包括目标数）都是正整数。
// 解集不能包含重复的组合。
// 示例 1:

// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
// 所求解集为:
// [
//   [1, 7],
//   [1, 2, 5],
//   [2, 6],
//   [1, 1, 6]
// ]
// 示例 2:

// 输入: candidates = [2,5,2,1,2], target = 5,
// 所求解集为:
// [
//   [1,2,2],
//   [5]
// ]

#include <vector>
#include <set>
#include <algorithm>

using namespace std;

// 回溯
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> result;
        vector<int> item;
        set<vector<int>> res_set;
        sort(candidates.begin(), candidates.end());
        generate(0, candidates, result, item, res_set, 0, target);
        return result;
    }
    void generate(int i, vector<int> &nums,
                  vector<vector<int>> &result,
                  vector<int> &item,
                  set<vector<int>> &res_set,
                  int sum, int target)
    {
        if (i >= nums.size() || sum > target) {
            return;
        }
        sum += nums[i];
        item.push_back(nums[i]);
        if (sum == target && res_set.find(item) == res_set.end()) {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i + 1, nums, result, item, res_set, sum, target);
        sum -= nums[i];
        item.pop_back();
        generate(i + 1, nums, result, item, res_set, sum, target);
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res{};
        vector<int> vec{};
        sort(candidates.begin(), candidates.end());
        backTrack(res, vec, candidates, 0, target);
        return res;
    }
    void backTrack(vector<vector<int>>& res, vector<int>& vec, const vector<int>& candidates, int start, int target) {
        if (target == 0) {
            res.push_back(vec);
        } else {
            for (int i{start}; i < candidates.size(); ++i) {
                if (target - candidates[i] < 0) break;
                if (i > start && candidates[i] == candidates[i-1]) continue; // 去掉重复，剪枝
                vec.push_back(candidates[i]);
                backTrack(res, vec, candidates, i + 1, target - candidates[i]);
                vec.pop_back();
            }
        }
    }
};

/* 回溯
*/
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        dfs(0, n, candidates, target);
        return res;
    }
    void dfs(int start, const int& n, const vector<int>& candidates, int target) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.emplace_back(temp);
            return;
        }
        for (int i{start}; i < n; ++i) {
            if (i > start && candidates[i] == candidates[i-1]) { // 去重
                continue;
            }
            temp.push_back(candidates[i]);
            dfs(i + 1, n, candidates, target - candidates[i]);
            temp.pop_back();
        }
    }
private:
    vector<vector<int>> res{};
    vector<int> temp{};
};

/* 递归 + 回溯
可以考虑将相同的数放在一起进行处理
我们还可以进行什么优化（剪枝）呢？
一种比较常用的优化方法是，我们将 freq 根据数从小到大排序，
这样我们在递归时会先选择小的数，再选择大的数。
*/
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (const auto& candidate : candidates) {
            if (freq.empty() || candidate != freq.back().first) {
                freq.emplace_back(candidate, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return res;
    }
    void dfs(int pos, int rest) {
        if (rest == 0) {
            res.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }
        dfs(pos + 1, rest);
        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i{1}; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i{1}; i <= most; ++i) {
            sequence.pop_back();
        }
    }
private:
    vector<pair<int, int>> freq{};
    vector<vector<int>> res{};
    vector<int> sequence{};
};